#include<stdio.h>
#include<string.h>

char arr[1000000][90];

int main()
{
    int T;
    int n,L;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&L);
        getchar();
        for(int i=0;i<n;i++)
        {
            gets(arr[i]);
        }
        for(int i =0;i<L;i++)
        {
            printf("*");
        }
        printf("\n");
        for(int i=0;i<n;i++)
        {
            printf("*");
            int len = strlen(arr[i]);
            int kong = L-2-len;
            for(int i =0;i<kong/2;i++)
            {
                printf(" ");
            }
            printf("%s",arr[i]);
            if(kong%2==0)
            {
                for(int i =0;i<kong/2;i++)
                {
                    printf(" ");
                }
            }
            else
            {
                for(int i =0;i<kong/2+1;i++)
                {
                    printf(" ");
                }
            }
            printf("*");
            printf("\n");
        }
        for(int i =0;i<L;i++)
        {
            printf("*");
        }
        printf("\n");
    }
    return 0;
}